package com.rui.study.algorithm.P_零杠一背包PLUS_动态规划;

/**
 * @program: study
 * @description:
 * @author: Yaowr
 * @create: 2018-12-29 15:31
 **/
public class Solution {

    public static int maxValue(int[] weight, int value[], int w) {
        Integer[] state = new Integer[w+1];             // 数组下标代表物品重量，元素值代表物品价值
        state[0] = 0;
        state[weight[0]] = value[0];

        for (int i = 1; i < weight.length; i++) {       // 动态规划，状态转移
            for (int j = 0; j <= w - weight[i]; j++) {
                if (state[j] != null) {
                    if (state[j+weight[i]] == null
                            || state[j+weight[i]] < state[j] + value[i]) {
                        state[j+weight[i]] = state[j] + value[i];
                    }
                }
            }
        }

        int maxV = Integer.MIN_VALUE;
        for (int i = w; i >= 0; i--) {
            if (state[i] != null && state[i] > maxV) maxV = state[i];
        }
        return maxV;
    }


    public static void main(String[] args) {
        System.out.println("最大价值：" + maxValue(new int[]{2, 3, 6, 7, 9},
                new int[]{4, 3, 3, 9, 6}, 12));
    }
}
